package com.ma.sort;


//基数排序(用例为非负整数)
public class radixSort {


    //O(N*log(10,Max))
    public static void run(int[] arr,int L,int R,int digit){
        final int radix=10;
        int i=0,j=0;
        int[] help=new int[R-L+1];
        for(int d=1;d<=digit;d++){
            int[] count=new int[radix];
            /*
            记录d位的各个0~9的数有几个
             */
            for(i=L;i<=R;i++){
                j=getDigit(arr[i],d);
                count[j]++;
            }
            /*
            与前一个先加，变成记录这个d位0~9的数的位置,再从后往前遍历他将他加到help位置
            (d=1即个位)
            arr= 100,22,11,20,12...
            0  2
            1  1
            2  2
            .
            .
            .
            9  0
            加完
            0  2
            1  3
            2  5
            .
            .
            .
            9  ?
            那么
               索引        剩余
            12 5-1  --  2  4
            20 2-1  --  0  1
            11 3-1  --  1  2
            22 4-1  --  2  3
            100 1-1  --  0  0

            这样按d位排序(d=1个位)就做完了: 100 20 11 12 22
            d++(位数++)如此反复
             */
            for(i=1;i<radix;i++){
                count[i]=count[i]+count[i-1];
            }
            for(i=R;i>=L;i--){
                j=getDigit(arr[i],d);
                help[count[j]-1]=arr[i];
                count[j]--;
            }
            for(i=L;i<=R;i++){
                arr[i]=help[i];
            }
        }


    }

    private static int getDigit(int i, int d) {
        for(int n=1;n<d;n++){
            i=i/10;
        }
        return i%10;

    }


}
